// 修改莫队
// https://www.luogu.com.cn/problem/P1903
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 1e6;
const int maxn = 5 + 133333;

int bsiz;
struct ASK {
    int l, r, c;
    int id;
    ll ans;
    bool operator<(const ASK &b) const { return id < b.id; }
} ask[maxn];
bool coder(const ASK &a, const ASK &b) {
    if (a.l / bsiz != b.l / bsiz) return a.l / bsiz < b.l / bsiz;
    if (a.r / bsiz != b.r / bsiz) return a.r / bsiz < b.r / bsiz;
    return a.c < b.c;
}

struct Update {
    int pos;
    int val;
} upd[maxn];

int n, m;
int a[maxn];
int clk, asiz;

ll now_ans; // sum(c_{cnt[x], 2})
int cnt[max_size];

void insert(int x) {
    if (++cnt[x] == 1) ++now_ans;
}
void erase(int x) {
    if (--cnt[x] == 0) --now_ans;
}

void update(ASK &i, Update &j) {
    if (i.l <= j.pos && j.pos <= i.r) {
        erase(a[j.pos]), insert(j.val);
    }
    swap(a[j.pos], j.val);
}

void modui() {
    bsiz = pow(n, 2.0 / 3);
    sort(ask + 1, ask + 1 + asiz, coder);
    int s = 1, t = 0, c = 0;
    for (int i = 1; i <= asiz; ++i) {
        int l = ask[i].l, r = ask[i].r, dfn = ask[i].c;
        while (l < s) insert(a[--s]);
        while (t < r) insert(a[++t]);
        while (s < l) erase(a[s++]);
        while (r < t) erase(a[t--]);
        while (c < dfn) update(ask[i], upd[++c]);
        while (dfn < c) update(ask[i], upd[c--]);
        ask[i].ans = now_ans;
    }
}

int main() {
    n = rad(), m = rad();
    rf(i, n) a[i] = rad();
    rf(i, m) {
        char op[5];
        scanf("%s", op);
        if (*op == 'Q') {
            ask[++asiz].l = rad(), ask[asiz].r = rad(), ask[asiz].c = clk, ask[asiz].id = asiz;
        } else if (*op == 'R') {
            upd[++clk].pos = rad(), upd[clk].val = rad();
        }
    }
    modui();
    sort(ask + 1, ask + 1 + asiz);

    rf(i, asiz) {
        printf("%d\n", ask[i].ans);
    }

    return 0;
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}